#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
typedef struct btnode
{
	char btdata;
	struct btnode* plch;
	struct btnode* prch;
}btn;
struct node
{
	btn* data;
	struct node* next;
};
typedef struct linkqueue
{
	struct node* f;
	struct node* r;
}lq;
lq* queueinit()
{
	lq* pq = (lq*)malloc(sizeof(lq));
	if (pq == NULL)
	{
		printf("malloc fail");
		return NULL;
	}
	pq->f = (struct node*)malloc(sizeof(struct node));
	if (pq->f == NULL)
	{
		free(pq);
		return NULL;
	}
	pq->r = pq->f;
	pq->f->next = NULL;
	return pq;
}
bool is_empty(lq* pq)
{
	if (pq->f == pq->r)
		return true;
	else
		return false;
}
bool enqueue(lq* pq, btn* data)
{
	struct node* newnode = (struct node*)malloc(sizeof(struct node));
	if (newnode == NULL)
	{
		printf("malloc fail");
		return false;
	}
	newnode->data = data;
	newnode->next = NULL;
	pq->r->next = newnode;
	pq->r = newnode;
	return true;
}
bool out_queue(lq* pq, btn** val)
{
	if (is_empty(pq))
		return false;
	*val = pq->f->next->data;
	struct node* tmp = pq->f->next;
	pq->f->next = tmp->next;
	if (pq->f->next == NULL)
		pq->r = pq->f;
	tmp->next = NULL;
	free(tmp);
	return true;
}
btn* create_tree()
{
	btn* pa, * pb, * pc, * pd, * pe;
	pa = (btn*)malloc(sizeof(btn));
	pb = (btn*)malloc(sizeof(btn));
	pc = (btn*)malloc(sizeof(btn));
	pd = (btn*)malloc(sizeof(btn));
	pe = (btn*)malloc(sizeof(btn));

	pa->plch = pb;
	pa->prch = pc;
	
	pb->plch = pd;
	pb->prch = pe;
	
	pc->plch = NULL;
	pc->prch = NULL;
	
	pd->plch = NULL;
	pd->prch = NULL;
	
	pe->plch = NULL;
	pe->prch = NULL;

	pa->btdata = 'a';
	pb->btdata = 'b';
	pc->btdata = 'c';
	pd->btdata = 'd';
	pe->btdata = 'e';
	return pa;
}
void level_show(btn* proot)
{
	lq* pq = queueinit();
	btn* tmp = proot;
	enqueue(pq, tmp);
	while (!is_empty(pq))
	{
		out_queue(pq, &tmp);
		if (tmp != NULL)
		{
			printf("%c\t", tmp->btdata);
			if (tmp->plch != NULL)
				enqueue(pq, tmp->plch);
			if (tmp->prch != NULL)
				enqueue(pq, tmp->prch);
		}
	}
}
void qian_show(btn* proot)
{
	if (proot != NULL)
	{
		printf("%c\t", proot->btdata);
		if (proot->plch != NULL)
			qian_show(proot->plch);
		if (proot->prch != NULL)
			qian_show(proot->prch);
	}
}
void middle_show(btn* proot)
{
	if (proot->plch != NULL)
		middle_show(proot->plch);
	printf("%c\t", proot->btdata);
	if (proot->prch != NULL)
		middle_show(proot->prch);
}
void last_show(btn* proot)
{
	if (proot->plch != NULL)
		last_show(proot->plch);
	if (proot->prch != NULL)
		last_show(proot->prch);
	printf("%c\t", proot->btdata);
}
int main()
{
	btn* proot = create_tree();
	//level_show(proot);
	printf("\n");
	//qian_show(proot);
	//middle_show(proot);
	last_show(proot);
	return 0;
}